Disk arrays comprising a multiplicity of small inexpensive disk drives, such as the 51/4 or 31/2 inch disk drives currently used in personal computers and workstations, connected in parallel have emerged as a low cost alternative to the use of single large disks for non-volatile storage of information within a computer system. The disk array appears as a single large fast disk to the host system but offers improvements in performance, reliability, power consumption and sealability over a single large magnetic disk. Several disk array alternatives are discussed in an article titled "A Case for Redundant Arrays of Inexpensive Disks (RAID)" by David A. Patterson, Garth Gibson and Randy H. Katz; University of California Report No. UCB/CSD 87/391, December 1987. The article, incorporated herein by reference, discusses disk arrays and the improvements in performance, reliability, power consumption and sealability that disk arrays provide in comparison to single large magnetic disks. Five disk array arrangements, referred to as RAID levels, are described. The simplest array, a RAID level 1 system, comprises one or more disks for storing data and an equal number of additional "mirror" disks for storing copies of the information written to the data disks. The remaining RAID levels, identified as RAID level 2, 3, 4 and 5 systems, segment the data into portions for storage across several data disks. One or more additional disks are utilized to store error check or parity information. The present invention is directed to improvements in the operation of RAID level 4 and 5 systems.
A RAID level 4 disk array is comprised of N+1 disks wherein N disks are used to store data, and the additional disk is utilized to store parity information. Data to be saved is divided into portions consisting of one or many blocks of data for storage among the disks. The corresponding parity information, which can be calculated by performing a bit-wise exclusive-OR of corresponding portions of the data stored across the N data drives, is written to the dedicated parity disk. The parity disk is used to reconstruct information in the event of a disk failure. Writes typically require access to two disks, i.e., one of the N data disks and the parity disk, as will be discussed in greater detail below. Read operations typically need only access a single one of the N data disks, unless the data to be read exceeds the block length stored on each disk.
RAID level 5 disk arrays are similar to RAID level 4 systems except that parity information, in addition to the data, is distributed across the N+1 disks in each group. Each one of the N+1 disks within the array includes some blocks for storing data and some blocks for storing parity information. Where parity information is stored is controlled by an algorithm implemented by the user. As in RAID level 4 systems. RAID level 5 writes typically require access to two disks; however, no longer does every write to the array require access to the same dedicated parity disk, as in RAID level 4 systems. This feature provides the opportunity to perform concurrent write operations.
A RAID level 5 system including five data and parity disk drives, DRIVE A through DRIVE E, and a spare disk drive, DRIVE F, is illustrated in FIG. 1. An array controller 100 coordinates the transfer of data between the host system 147 and the array disk drives. The controller also calculates and checks parity information. Blocks 145A through 145E illustrate the manner in which data and parity is stored on the five array drives. Data blocks are identified as BLOCK 0 through BLOCK 15. Parity blocks are identified as PARITY 0 through PARITY 3. The relationship between the parity and data blocks is as follows:
PARITY 0=(BLOCK 0) XOR (BLOCK 1) XOR (BLOCK 2) XOR (BLOCK 3) PA0 PARITY 1=(BLOCK 4) XOR (BLOCK 5) XOR (BLOCK 6) XOR (BLOCK 7) PA0 PARITY 2=(BLOCK 8) XOR (BLOCK 9) XOR (BLOCK 10) XOR (BLOCK 11) PA0 PARITY 3=(BLOCK 12) XOR (BLOCK 13) XOR (BLOCK 14) XOR (BLOCK 15)
As stated above, parity data can be calculated by performing a bit-wise exclusive-OR of corresponding portions of the data stored across the N data drives. However, because each parity bit is simply the exclusive-OR product of all the corresponding data bits from the data drives, new parity can be more easily determined from the old data and the old parity as well as the new data in accordance with the following equation: EQU new parity=(old data XOR new data) XOR old parity.
Although the parity calculation for RAID levels 4 or 5 shown in the above equation is much simpler than performing a bit-wise exclusive-OR of corresponding portions of the data stored across all of the data drives, a typical RAID level 4 or 5 write operation will require a minimum of two disk reads and two disk writes. More than two disk reads and writes are required for data write operations involving more than one data block. Each individual disk read operation involves a seek and rotation to the appropriate disk track and sector to be read. The seek time for all disks is therefore the maximum of the seek times of each disk. A RAID level 4 or 5 system thus carries a significant write penalty when compared with a single disk storage device or with RAID level 1, 2 or 3 systems.
One method for decreasing the RAID level 4 and 5 write penalty is to perform an early write operation wherein write data received from the host is written into a transfer buffer and a write complete status signal provided back to the host. The array controller completes the read-modify-write operation at a later, more convenient time. Drive utilization efficiency and I/O response time for read-modify-write operations may be also be improved by separating the execution of data read and write operations from the execution of parity read, generation and write operations. The improved read-modify-write operation identifies the disk drives containing the data and parity to be updated and places the proper read and write requests into the I/O queues for the identified data and parity drives, scheduling some or all parity operations; i.e. reading old parity information from the parity drive, generating new parity information and writing the new parity information to the parity drive; for execution when best accommodated in the I/O queue for the parity drive, following the read of old data from the data drive. A write completion status signal is provided to the host system just after the write of data to the data drive is completed, without waiting for the associated parity generation and write to of new parity information to the parity drive to complete.
The two strategies discussed above for reducing array write penalties are not without shortcomings. Possible problems which may arise with the implementation of these early write procedures include:
1. A power failure following issuance of the write complete status signal to the host, but before completion of write operations to transfer data and parity from the transfer buffer to disk could result in the loss of data.
2. Should the disk array subsystem experience a controller failure prior to the completion of write operation, there exists no method for transferring the data written into the transfer buffer to a replacement controller.
3. Although a battery backup can be provided to protect against a power failure, there are severe time constraints which limit the continued operation of the array during a protracted power loss.
4. A transfer buffer providing full speed data transfer capabilities supported by a battery backup can be provided to protect against data loss, however, a RAM buffer that is fast enough to be used for full speed data transfers is typically very expensive or power hungry. These constrains require the use of large batteries, multiple batteries, or batteries which are contained off the controller board.
A method and structure for safeguarding disk array early write operations is required to prevent the data loss resulting from the occurrence of a power failure or array failure prior to completion of all write procedures.